package com.gitee.wsl.ext.array.sort

import com.gitee.wsl.ext.array.flip

/**
 * Pancake sort is a sorting algorithm that sorts a sequence by repeatedly flipping the elements.
 * In each iteration, it finds the maximum element and flips the subsequence from the first element
 * up to the maximum element.
 * This process is repeated until the sequence is sorted.
 *
 * Worst-case performance:       O(n^2)
 * Best-case performance:        O(n)
 * Average performance:          O(n^2)
 * Worst-case space complexity:  O(1)
 */
fun<T : Comparable<T>> Array<T>.pancakeSort(){
    for (i in this.indices) {
        var max = this[0]
        var index = 0

        for (j in 0 until this.size - i) {
            if (max < this[j]) {
                max = this[j]
                index = j
            }
        }
        this.flip(index, this.size - 1 - i)
    }
}